Năm 1761, Mikhail Illarionovich tốt nghiệp với quân hàm chuẩn úy. Nhờ vốn ngoại ngữ phong phú, thành tích học tập xuất sắc cùng thái độ cư xử tốt, tháng 3/1762, Kutuzov được bổ nhiệm làm sĩ quan phụ tá cho thống đốc tỉnh Reven, nguyên soái Holstein-Bergskyi. Trong thời gian này, Kutuzov có dịp tiếp xúc với nhiều yếu nhân trong quân đội và chính khách ngoại quốc.

Tháng 7 năm đó, Sa hoàng Pyotr III bị hoàng hậu Ekaterina hạ bệ và sau đó sát hại để đoạt ngôi. Do là một cận thần của Pyotr I, nguyên soái Holstein-Bergskyi bị nữ hoàng Ekaterina cách chức. Còn Kutuzov được điều vào quân ngũ và giữ chức chỉ huy đại đội trong trung đoàn bộ binh Astrakhan do đại tá Aleksandr Vasilyevich Suvorov chỉ huy.[8]

Ở đây, Kutuzov được mục kích cảnh sinh hoạt và huấn luyện quân đội mới: mọi người đều phải luyện tập theo nguyên tắc khắc nghiệt của Suvorov: "luyện tập nặng, chiến đấu nhẹ", tuy nhiên binh sĩ lại được ăn no, mặc ấm, không hề bị đánh đập hay lăng mạ. Bản thân đại tá Suvorov được đánh giá là một sĩ quan chỉ huy luôn thấu hiểu binh sĩ và tôn trọng sáng kiến họ. Sau mỗi buổi tập, Suvorov thường cùng ngồi trò chuyện, đùa vui, tán gẫu và lắng nghe tâm sự của binh sĩ. Ông cũng lập ra một lớp học dành cho con em của họ, đồng thời kiêm luôn nhiệm vụ giáo viên và biên soạn giáo trình cho các học trò.[8]

Suvorov cũng sớm phát hiện và bồi dưỡng tài năng của Kutuzov. Ông kể cho Kutuzov nghe về con đường tiến thân của mình, giảng rằng sức mạnh của quân đội nằm ở binh lính, vì vậy cần phải làm cho người lính hiểu rõ về chiến tranh và sẵn sàng chiến đấu ngay trong thời bình. Suvorov đã dạy cho Kutuzov về các kĩ năng chỉ huy quân đội, sự cần thiết về tính đơn giản và chuẩn xác của mỗi mệnh lệnh trong tác chiến. Nguyên soái Suvorov cũng dạy cho cậu học trò của ông rằng trách nhiệm không thể thiếu của các sĩ quan lãnh đạo là phải quan tâm, chăm lo cho sức khỏe và đời sống của binh sĩ, phải gần gũi với các thuộc cấp và phải xông pha ở tuyến đầu trận đánh để làm gương cho các binh sĩ noi theo. Tất cả những điều đó đã phần nào hình thành phong cách cầm quân của Kutuzov sau này.[9]

Năm 1764, Kutuzov được điều sang Ba Lan để tham chiến. Gần một năm sau, ông về nước làm việc ở Hội đồng Mật viện quốc gia (tên gọi thượng viện Nga thời Ekaterina II), dưới quyền của chưởng lý, công tước Vyazemskyi. Sau đó, ông tham gia ban thư ký của Ủy ban soạn thảo dự luật mới. Tháng 12/1768, nữ hoàng Nga giải tán ủy ban và điều Kutuzov trở lại quân ngũ, sang Ba Lan lần thứ hai để trấn áp cuộc khởi nghĩa của Liên minh Bar. Trong thời gian này, Kutuzov tự nhận: "Chúng tôi sống rất vui, đánh nhau với người Ba Lan, nhưng tôi chưa hiểu về chiến tranh."[8] Ở Ba Lan, Kutuzov đã lập được một số chiến công và bước đầu chứng tỏ được năng lực quân sự của mình.[10]

Chiến tranh Nga-Thổ (1768-1774)

Năm 1770, Kutuzov được điều sang quân đoàn Nga do nguyên soái Pyotr Aleksandrovich Rumyantsev chỉ huy đang chiến đấu tại Moldavia và Wallachia chống lại các lực lượng chủ lực của liên quân Ottoman-Hãn quốc Krym. Quân Nga luôn phải chiến đấu trên một chiến trường hoang vu, hẻo lánh, nơi đường sá và dân cư thưa thớt, trong khi bị quân Ottoman áp đảo về quân số. Nhưng hoàn cảnh khó khăn đó đã giúp Kutuzov học hỏi được nhiều kinh nghiệm mới.[11]

Nguyên soái Rumyantsev thực hành một lối đánh mới: Rumyantsev trực tiếp chỉ huy 20.000 quân, phần còn lại được chia nhỏ thành các đơn vị độc lập gồm 4-8 nghìn quân, có nhiệm vụ phối hợp công kích đối phương từ nhiều hướng. Kutuzov tham gia chiến đấu với vai trò sĩ quan cận vệ trong đơn vị có nhiệm vụ tác chiến ở vùng trung tâm. Ông được giao nhiệm vụ trinh sát, phân tích sự chuyển quân của cả hai bên, tham gia thảo kế hoạch hành động của quân đoàn và phối hợp cùng các lực lượng dự bị chiến đấu ở những nơi nguy hiểm. Khi chiến đấu, Kutuzov luôn tỏ ra dũng cảm, lập nhiều chiến công và thể hiện sự đa tài trên nhiều lĩnh vực. Mùa thu năm 1771, Kutuzov tham gia trận đánh ở Popesti, nơi quân Nga đánh tan 3 vạn quân Thổ. Sau đó, ông được khen thưởng về lòng dũng cảm và được thăng lên quân hàm thượng tá.[11]

Tuy nhiên, một bạn học cũ của Kutuzov đã bí mật nói với Rumyantsev về việc ông nhái lại các động tác của vị nguyên soái nhằm mua vui cho đồng đội. Vốn là một người dễ tự ái, Rumyantsev đã nổi giận; nhưng chính lòng dũng cảm và những chiến công đã cứu Kutuzov thoát khỏi nguy cơ bị kỉ luật, nhưng vẫn bị thuyên chuyển sang Tập đoàn quân số 2 của hoàng thân Vasili Dolgorukov-Krymsky đóng tại Krym, và thậm chí không được trao huân chương khích lệ. Biến cố này đã biến ông thành một người kín đáo và đa nghi, dù vẫn giữ vẻ ngoài vui vẻ, giao thiệp rộng.[11]

Ở Krym, Kutuzov tiếp tục đảm nhận vai trò của một sĩ quan chỉ huy luôn tác chiến ở những nơi nguy hiểm trên trận địa, từ đó mà tích lũy một kinh nghiệm sẽ giúp ích rất nhiều trong tương lai: kỹ năng điều phối các đơn vị kỵ binh Cossack. Ngày 22/7/1774, trong trận công kích pháo đài Alushta, nhằm khôi phục lại sức mạnh tiến công đang bị suy giảm của quân Nga sau những đợt công kích không thành, Kutuzov đã cầm cờ xông thẳng tới trước trận tuyến để làm gương cho binh sĩ, nhưng bị trúng đạn vào điểm giữa mắt phải và thái dương của Kutuzov. Tuy vết thương không nguy hiểm đến tính mạng, nhưng việc điều trị rất phức tạp và cần một năm rưỡi để hồi phục.[11]

Trong thời gian này, Kutuzov lần đầu gặp Ekaterina Ilynina Bibikova, người vợ tương lai của ông, tại một buổi tiệc ở nhà người chú Ivan Loginovich. Theo một số nguồn, Kutuzov đem lòng yêu Ekaterina vì sự xinh đẹp và thông minh của bà, còn tiểu thư Ekaterina cũng đáp lại tình yêu của Kutuzov mà gia tộc Bibikov cũng không phản đối. Năm 1775, hai người kết hôn với nhau, cùng lúc Kutuzov được trao huy chương đầu tiên - huân chương Thánh Georghi hạng tư - và được cho nghỉ phép một năm để ra nước ngoài chữa bệnh.[11] Nguyên do là tình trạng đau nhức ở vùng mắt bị thương vẫn không suy giảm và Kutuzov quyết định đến Phổ để được trị liệu tốt hơn.

Kutuzov nhân dịp đó đi thăm thú nhiều nước Tây Âu. Vào năm 1774, ông đến Berlin (vương quốc Phổ) diện kiến vua Friedrich II (hay còn được gọi là Friedrich đại đế) - người đưa nước Phổ giành thắng lợi trong cuộc Chiến tranh Bảy năm và cuộc Chia cắt Ba Lan vừa qua. Ngay sau đó, Kutuzov được chữa trị bởi các quan ngự y của vua Friedrich, và hai người dành nhiều thời gian bàn luận về chiến thuật, quân khí và quân phục. Từ Berlin, Kutuzov đến Leyden (Hà Lan), một trung tâm học thuật lớn của châu Âu đương thời. Ông nghỉ ngơi tại đây vài tuần và được các bác sĩ điều trị mắt. Sau đó, anh vượt qua eo biển Manche đến nước Anh. Khi đó, mọi người ở London đều bàn tán sôi nổi về cuộc cách mạng Mỹ do George Washington lãnh đạo chống lại sự cai trị của thực dân Anh.

Trong suốt thời gian ở đây, Kutuzov đã có cơ hội tham khảo các chiến dịch quân sự trong cuộc kháng chiến này và rút ra được một kết luận: nếu muốn chiến thắng một cuộc chiến thì không nhất thiết phải chiến thắng tất cả các trận đánh nhỏ (cuộc cách mạng sau đó kết thúc vào năm 1783 dẫn đến sự thành lập nước Hoa Kỳ độc lập, bất chấp những thắng lợi của quân Anh). Trở lại châu Âu lục địa, Kutuzov tiếp tục hành trình về Vienna năm 1775. Tại đây, ông gặp gỡ những tướng lĩnh hàng đầu của quân đội Áo, trong đó có bá tước Ernst Gideon von Laudon - người chỉ huy liên quân Nga - Áo đánh bại quân Phổ của vua Friedrich II trong trận Kunersdorf 7 năm trước (12/8/1759). Cuối cùng, sau một chuyến viếng thăm ngắn ở Ý, Kutuzov về nước vào cuối năm 1776.[11][12][13]

Gặp lại và cùng chiến đấu với thầy cũ (1777-1791)

Trở về Nga năm 1777, Kutuzov được thăng hàm đại tá và được bổ nhiệm làm chỉ huy trưỏng một trung đoàn ở Krym dưới quyền chỉ huy của người thầy cũ: Aleksandr Suvorov. Mặc dù hãn quốc Krym đã độc lập nhưng đế quốc Ottoman vẫn duy trì ảnh hưởng tại đây, buộc Suvorov phải khéo léo kết hợp các biện pháp ngoại giao và quân sự để giữ vững ưu thế của Nga. Khi đó, Kutuzov trở thành cánh tay phải đắc lực của Suvorov. Bản thân Kutuzov cũng học hỏi thêm được nhiều kiến thức quân sự, trong đó đáng chú ý là học thuyết "khoa học chiến thắng" của Suvorov. Học thuyết này cùng các phương pháp huấn luyện mới do Suvorov đúc kết sẽ giúp ích rất nhiều cho Kutuzov sau này.[14]

Năm 1782, Kutuzov được thăng hàm chuẩn tướng. Năm 1784, ông kết thúc nhiệm vụ tại Krym và được phong quân hàm thiếu tướng theo đề nghị của Suvorov, sau đó được giao chỉ huy một trong các quân đoàn bộ binh cơ động đầu tiên được thành lập theo sáng kiến của Suvorov[14]. Năm 1785, ông giữ chức trung đoàn trưởng trung đoàn kị binh Bugshi do ông thành lập. Tuy nhiên, niềm vui của Kutuzov không trọn vẹn vì cha ông, Illarion Matveevich, từ trần trước khi biết tin con mình được phong tướng[14]. Đến năm 1787, Kutuzov trở thành thống đốc tỉnh Krym.

Chiến tranh Nga-Thổ (1787-1791) và trận pháo đài Izmail

Trong năm 1787, chiến tranh Nga-Thổ lại bùng nổ. Kutuzov tham gia nhiều trận đánh và lập một số chiến công. Lực lượng của ông tham gia các trận chiến chống quân Thổ dọc theo khu vực biên giới Nga ở sông Bog (nay thuộc lãnh thổ Ukraina). Mùa hè năm 1788, ông chỉ huy kị binh nhẹ Cossack tham gia trận pháo đài Ochakov và bị thương lần thứ hai, khi một viên đạn găm vào vùng gần vết thương cũ ở mắt. Mặc dù không bị nguy hiểm tính mạng, nhưng vết thương này đã làm suy giảm thị lực của mắt phải Kutuzov và các cơn đau đầu trở nên trầm trọng hơn.[14][15] Sau đó, ông còn tham gia các trận đánh ở Bender và Akerman.

Ngày 13/12/1790, quân Nga mở một đợt tấn công quyết định, với mục tiêu là pháo đài Izmail kiên cố nhằm kiểm soát được bờ sông Danube. Suvorov được giao nhiệm vụ tấn công pháo đài, nên ông giao cho Kutuzov chỉ huy cánh quân thứ 6 bên cánh trái. Đến sáng ngày 22/12, Kutuzov chỉ huy binh sĩ tiến vào từ Kiliya ở phía đông Izmail mở đường cho các cánh quân khác cùng tiến vào trong trung tâm pháo đài. Tuy nhiên, quân Nga bị áp đảo về quân số so với đối thủ, buộc Kutuzov xin Suvorov yểm trợ, nhưng ông nhận được câu trả lời kỳ quặc: "Báo cáo về việc chiếm thành Ismail và việc cử Kutuzov làm chỉ huy trưởng pháo đài đã được gửi về Saint Petersburg".[16]

Kutuzov tiếp tục huy động các lực lượng bộ binh cơ động, ồ ạt xung phong chọc thủng phòng tuyến quân Thổ, mở đường vào pháo đài. Quân Thổ chống cự quyết liệt nhưng do thua kém quân Nga về trình độ tổ chức, kỹ thuật nên pháo đài thất thủ. Toàn bộ số quân Thổ tại Ismail đều chết hoặc bị bắt sống. Về sau, khi gặp lại Kutuzov trong pháo đài, Suvorov đã nói rằng ông và Kutuzov luôn hiểu nhau, nếu không hạ được Ismail thì cả hai đã chết dưới chân thành.[14] Suvorov cũng đánh giá rất lớn công lao của Kutuzov tại Ismail, báo cáo của ông gửi về kinh đô có đoạn:

Quân Nga tổn thất hàng nghìn người, trong đó một phần đáng kể là các sĩ quan vì họ luôn đi trước nêu gương cho binh sĩ. Trong thư gửi cho vợ ngày 12/12/1790, Kutuzov miêu tả:

Sau chiến thắng này, Suvorov giao cho Kutuzov nhiệm vụ phòng thủ pháo đài Izmail[16]. Ông cũng chỉ huy các quân đoàn đóng giữa sông Dnepr và sông Pruth.[14] Đến ngày 15/6/1791, ông mở cuộc đột kích bất ngờ đánh tan 20.000 quân Thổ tại Baladag.